package com.jc.algorithmes.binarytree;


import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 二叉树的层序遍历：
 * 1.先遍历第一层节点，再遍历第二层节点，依次类推
 * 2.采用递归法实现
 */

public class LevelOrderDemo {

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7,null,null);
        TreeNode node6 = new TreeNode(6,null,null);
        TreeNode node5 = new TreeNode(5,node6,node7);
        TreeNode node4 = new TreeNode(4,null,null);
        TreeNode node3 = new TreeNode(3,null,null);
        TreeNode node2 = new TreeNode(2,node4,node5);
        TreeNode node1 = new TreeNode(1,node2,node3);

        ArrayList list = new ArrayList();
        levelOrder(node1,1,list);
        System.out.println(Arrays.toString(list.toArray()));

    }

    public static void levelOrder(TreeNode root, int i, ArrayList list){
        if(root == null){
            return;
        }
        int length = list.size();
        if (length <= i){
            for (int j = 0;j<= i-length; j++){
                list.add(length+j,null);
            }
        }

        list.set(i,root.val);
        levelOrder(root.left,2*i,list);
        levelOrder(root.right,2*i+1,list);

    }
}
